Sau khi vua Rajasanagara qua đời năm 1389, Majapahit bắt đầu suy vong, trước tiên là do tranh giành ngôi báu và tiếp theo là do sự nổi lên của vương quốc Melaka ở bán đảo Mã Lai như một trung tâm thương mại và một tiêu điểm truyền bá đạo Hồi vào Đông Nam Á.

Kế vị Rajasanagara là con gái ông, công chúa Kusumawardhani, mặc dù ông vẫn có con trai là hoàng tử Wirabhumi. Nội chiến đã xảy ra giữa hai chị em từ năm 1401 đến năm 1406, và kết cục là hoàng tử Vikramavardhana, chồng của công chúa Kusumawardhani đã chiến thắng và lên làm vua. Cuộc nội chiến đã tạo ra thời cơ cho nhiều chư hầu của Majapahit ly khai khỏi sự khống chế của Majapahit.

Đầu thế kỷ 15, Hồi quốc Malacca nổi lên ở eo biển Malacca, và tranh giành với Majapahit quyền thương mại hàng hải, góp phần làm suy yếu Majapahit. Những chuyến du hành các nước Đông Nam Á của Trịnh Hòa, một đô đốc theo đạo Hồi của nhà Minh, đã tạo cơ sở cho cộng đồng người Ả Rập và Hoa theo đạo Hồi nhập cư vào các cảng thị ở phía bắc Java như Semarang, Demak, Tuban, và Ampel. Các cộng đồng người Hồi này ngày càng phát triển và một số Hồi quốc đã được thành lập ở những nơi đó. Hồi quốc Demak sau này đã tiêu diệt Majapahit. Những nghệ sĩ, thợ thủ công theo đạo Hindu của Majapahit di cư tới đảo Bali, và đây là một trong chỉ vài nơi hiếm hoi của Indonesia ngày nay còn theo đạo Hindu.